home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 23 / AACD 23.iso / AACD / Online / opennap / hash.c < prev    next >
C/C++ Source or Header  |  2001-06-08  |  4KB  |  206 lines
  1. /* Copyright (C) 2000-1 drscholl@users.sourceforge.net
  2.    This is free software disributed under the terms of the
  3.    GNU Public License.  See the file COPYING for details.
  4.  
  5.    $Id: hash.c,v 1.15 2001/02/15 08:39:45 drscholl Exp $ */
  6.  
  7. /* Modified 30/05/01 : Changed a C++ style // comment to a C style comment
  8.       for Amiga port : to permit compiling with Amiga GCC 2.7.0
  9. */
  10.  
  11. #include <string.h>
  12. #include <ctype.h>
  13. #include <stdlib.h>
  14. #include "hash.h"
  15. #include "debug.h"
  16. #ifdef WIN32
  17. /* this is needed for the WIN32 port #def's */
  18. #include "opennap.h"
  19. #endif
  20.  
  21. /* a simple hash table.  keys are case insensitive for this application */
  22.  
  23. int
  24. hash_compare_string (void *a, void *b)
  25. {
  26.     return strcasecmp (a, b) == 0 ? 0 : -1;
  27. }
  28.  
  29. /* initialize a hash table.  `buckets' should be a prime number for maximum
  30.    dispersion of entries into buckets */
  31. HASH   *
  32. hash_init (int buckets, hash_destroy f)
  33. {
  34.     HASH   *h = CALLOC (1, sizeof (HASH));
  35.  
  36.     if (!h)
  37.         return 0;
  38.     h->numbuckets = buckets;
  39.     if ((h->bucket = CALLOC (buckets, sizeof (HASHENT *))) == 0)
  40.     {
  41.         FREE (h);
  42.         return 0;
  43.     }
  44.     h->destroy = f;
  45.     h->hash_key = hash_string;  /* default */
  46.     h->compare_key = hash_compare_string;
  47.     return h;
  48. }
  49.  
  50. void
  51. hash_set_hash_func (HASH * h, hash_key_t f, hash_compare_t comp)
  52. {
  53.     h->hash_key = f;
  54.     h->compare_key = comp;
  55. }
  56.  
  57. unsigned int
  58. hash_string (void *pkey)
  59. {
  60.     char   *key = (char *) pkey;
  61.     unsigned long h = 0, g;
  62.  
  63.     ASSERT (key != 0);
  64.     for (; *key; key++)
  65.     {
  66.         h = (h << 4) + tolower (*key);
  67.         if ((g = h & 0xF0000000))
  68.             h ^= g >> 24;
  69.         h &= ~g;
  70.     }
  71.     return h;
  72. }
  73.  
  74. unsigned int
  75. hash_pointer (void *key)
  76. {
  77. #if SIZEOF_LONG == 8
  78. #define BITS 3
  79. #else
  80. #define BITS 2
  81. #endif
  82.     return ((u_int) key) >> BITS;
  83. }
  84.  
  85. unsigned int
  86. hash_u_int (void *key)
  87. {
  88.     return (u_int) key;
  89. }
  90.  
  91. int
  92. hash_compare_u_int (void *a, void *b)
  93. {
  94.     return (a == b) ? 0 : -1;
  95. }
  96.  
  97. int
  98. hash_add (HASH * table, void *key, void *data)
  99. {
  100.     HASHENT *he = CALLOC (1, sizeof (HASHENT));
  101.     unsigned int sum;
  102.  
  103.     if (!he)
  104.         return -1;
  105.     ASSERT (key != 0);
  106.     ASSERT (data != 0);
  107.     ASSERT (table != 0);
  108.     he->key = key;
  109.     he->data = data;
  110.     sum = table->hash_key (key) % table->numbuckets;
  111.     he->next = table->bucket[sum];
  112.     table->bucket[sum] = he;
  113.     table->dbsize++;
  114.     return 0;
  115. }
  116.  
  117. void   *
  118. hash_lookup (HASH * table, void *key)
  119. {
  120.     HASHENT *he;
  121.     unsigned int sum;
  122.  
  123.     if (!table)
  124.         return 0;
  125.     ASSERT (key != 0);
  126.     sum = table->hash_key (key) % table->numbuckets;
  127.     he = table->bucket[sum];
  128.  
  129.     for (; he; he = he->next)
  130.     {
  131.         if (table->compare_key (key, he->key) == 0)
  132.             return he->data;
  133.     }
  134.     return 0;
  135. }
  136.  
  137. int
  138. hash_remove (HASH * table, void *key)
  139. {
  140.     HASHENT **he, *ptr;
  141.     unsigned int sum;
  142.  
  143.     ASSERT (table != 0);
  144.     ASSERT (key != 0);
  145.     sum = table->hash_key (key) % table->numbuckets;
  146.     for (he = &table->bucket[sum]; *he; he = &(*he)->next)
  147.     {
  148.         if (table->compare_key (key, (*he)->key) == 0)
  149.         {
  150.             ptr = (*he)->next;
  151.             if (table->destroy)
  152.                 table->destroy ((*he)->data);
  153.             FREE (*he);
  154.             table->dbsize--;
  155.             *he = ptr;
  156.             return 0;
  157.         }
  158.     }
  159.     return -1;
  160. }
  161.  
  162. void
  163. free_hash (HASH * h)
  164. {
  165.     HASHENT *he, *ptr;
  166.     int     i;
  167.  
  168.     ASSERT (h != 0);
  169.     /* destroy remaining entries */
  170.     for (i = 0; i < h->numbuckets; i++)
  171.     {
  172.         he = h->bucket[i];
  173.         while (he)
  174.         {
  175.             ptr = he;
  176.             he = he->next;
  177.             if (h->destroy)
  178.                 h->destroy (ptr->data);
  179.             FREE (ptr);
  180.         }
  181.     }
  182.     FREE (h->bucket);
  183.     FREE (h);
  184. }
  185.  
  186. void
  187. hash_foreach (HASH * h, void (*func) (void *, void *), void *funcdata)
  188. {
  189.     HASHENT *he, *ptr;
  190.     int     i;
  191.  
  192.     for (i = 0; i < h->numbuckets; i++)
  193.     {
  194.         he = h->bucket[i];
  195.         while (he)
  196.         {
  197.             /* we use a temp pointer here so that we can remove this entry
  198.                from the hash table inside of `func' and not cause problems
  199.                iterating the rest of the bucket */
  200.             ptr = he;
  201.             he = he->next;
  202.             func (ptr->data, funcdata);
  203.         }
  204.     }
  205. }
  206.